package com.coding.basic.stack;

import java.util.EmptyStackException;

/**
 * 设计一个栈，支持栈的push和pop操作，以及第三种操作findMin, 它返回改数据结构中的最小元素
 * finMin操作最坏的情形下时间复杂度应该是O(1) ， 简单来讲，操作一次就可以得到最小值
 *
 * @author liuxin
 */
public class QuickMinStack {

    private Stack<Integer> normalStack = new Stack<Integer>();
    private Stack<Integer> minNumStack = new Stack<Integer>();

    public void push(int data){

        normalStack.push(data);

        if(minNumStack.isEmpty()){
            minNumStack.push(data);
        } else{
            if(minNumStack.peek() >= data) {
                minNumStack.push(data);
            }
        }

    }
    public int pop(){
        if(normalStack.isEmpty()){
            throw new RuntimeException("the stack is empty");
        }
        int value = normalStack.pop();
        if(value == minNumStack.peek()){
            minNumStack.pop();
        }
        return value;
    }
    public int findMin(){
        if(minNumStack.isEmpty()){
            throw new RuntimeException("the stack is empty");
        }
        return minNumStack.peek();
    }
}
//public class QuickMinStack extends Stack<Integer> {
//
//    private Integer min;
//
//    public Integer push(Integer data) {
//        super.push(data);
//        if (min == null) {
//            min = data;
//        } else if (min > data) {
//            min = data;
//        }
//
//        return data;
//    }
//
//    public Integer pop() {
//        Integer pop = super.pop();
//        if (min != null && min.equals(pop)) {
//            min = null;
//        }
//
//        return pop;
//    }
//
//    public int findMin() {
//        if (super.size <= 0) {
//            throw new EmptyStackException();
//        }
//
//        if (min != null) {
//            return min;
//        }
//
//        int min = (int) super.dataArray[0];
//        for (int i = 1; i < super.size; i++) {
//            int data = (int) super.dataArray[i];
//            if (min > data) {
//                min = data;
//            }
//        }
//
//        this.min = min;
//
//        return min;
//    }
//}
